package com.tang.algorithm.string;

/**
 * @author tlm
 * @version 1.0
 * @date 2020/5/19 17:13
 * 验证回文字符串 Ⅱ
 * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
 * 示例 1:
 * <p>
 * 输入: "aba"
 * 输出: True
 * 示例 2:
 * <p>
 * 输入: "abca"
 * 输出: True
 * 解释: 你可以删除c字符。
 * 注意:
 * <p>
 * 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-palindrome-ii
 */
public class LeetCode680 {
    public static void main(String[] args) {
        System.out.println(validPalindrome("eeccccbebaeeabebccceea"));
    }

    public static boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        char[] c = s.toCharArray();
        while (left < right) {
            if (c[left] == c[right]) {
                left++;
                right--;
            } else {
                //不相等则删除左边或右边的字符，并验证剩余部分是否为回文串
                boolean flag1 = true, flag2 = true;
                for (int i = left, j = right - 1; i < j; i++, j--) {
                    if (c[i] != c[j]) {
                        flag2 = false;
                        break;
                    }

                }
                for (int i = left + 1, j = right; i < j; i++, j--) {
                    if (c[i] != c[j])
                    {
                        flag1 = false;
                        break;
                    }
                }
                return flag1 || flag2;
            }
        }

        return true;
    }


}
